package stu.day48;

import java.util.List;

public class hw2 {


    class Tire{

        class Treenode{
            boolean flag = false;
            Treenode[] children = new Treenode[26];
        }

        Treenode root = new Treenode();

        void insert(String str){
            Treenode node = root;
            for (char ch:str.toCharArray()){
                int n = ch-'a';
                if(node.children[n]==null){
                    node.children[n] = new Treenode();
                }
                node = node.children[n];
            }
            node.flag = true;
        }

        String search(String str){
            StringBuilder sb = new StringBuilder();
            Treenode node = root;
            int index = 0;
            for (char ch:str.toCharArray()){
                int m = ch -'a';
                if(node.children[m]==null) break;
                sb.append(ch);
                if(node.children[m].flag==true){
                    index = 1;
                    break;
                }
                node = node.children[m];
            }
            if(index==0){
                return str;
            }else {
                return sb.toString();
            }
        }


    }


    public String replaceWords(List<String> dictionary, String sentence) {

        Tire t = new Tire();
        for(String s:dictionary){
            t.insert(s);
        }

        StringBuilder sb = new StringBuilder();
        String[] str = sentence.split(" ");
        for (String m :str){
            String p = t.search(m);
            sb.append(p).append(" ");
        }

        return sb.toString().substring(0,sb.length()-1);



    }






}
